Modern computer and communications systems utilize large amounts of data. As a result data management and data storage have become significant technical issues when using modem computer and communications systems. Multimedia applications (e.g., applications which utilize video, audio, text, graphic, images) often have large data requirements which implicate large amounts of storage. Modern multimedia storage systems need to be able to manipulate both continuous media data such as video and audio, and conventional data such as text, graphics and images.
In current multimedia storage systems, data is often housed in a secondary storage media (e.g., magnetic disk) as blocks of data (one block consist of a series of contiguous bits). The data is then read from the secondary storage media into temporary memory e.g., cache which consist of random access memory (RAM)!, and then accessed by clients for use. FIG. 1 displays an illustrative architecture that manipulates multimedia data. In FIG. 1 secondary storage media such as a disk 10, is commonly used to store multimedia data. It should be appreciated that the secondary storage media may be a hard drive, an optical disk, or a mass storage system.
Data is typically housed in disk 10. In normal operations the disk 10 continuously rotates with a disk head (a device used to read data from the disk) raised above the disk 10. To read data from the disk 10 the disk head moves inward in a direction denoted by 13, the disk head is then lowered close to the disk 10 so that the disk head can read the data from the disk 10. The time it takes the disk to make one complete revolution is typically called the rotation time, the time it takes the disk head to move over the required data in a direction denoted by 13 is typically called the seek time, and the time required or the disk head to lower over the disk 10, is typically called the settle time.
After data blocks are located on the disk 10, the data blocks are usually read from the disk into a temporary memory area, typically known as the cache memory 30. To transmit data from the disk 10, into cache memory 30 requires that the data is first located on the disk, read from the disk, and then transferred into the cache. The entire process of finding the data blocks, reading the data blocks from the disk, and then transferring the data blocks into the cache is called the disk input/output(disk I/O).
Disk I/O is often limited by the disk bandwidth 20. The disk bandwidth 20 can be thought of as a pipe through which data flows. Normally the pipe has a limited amount of capacity (e.g. 44 Mbps), and only a certain amount of data can flow through the pipe per unit time. Therefore while tremendous amounts of data may be needed from the disk 10, the disk bandwidth 20 limits the speed at which the data can be transferred.
Client access to the cache memory 30 is managed by an admission controller 35. When clients (denoted by 50, 60 and 70) request access to the cache memory 30, the admissions controller determines if there is enough buffer space and disk bandwidth to accommodate the clients request. Once a client has been given access to the cache 3 0 by the admission controller 35, management of the cache memory 30 is performed by a buffer manager 40. The buffer manager 40 manipulates the cache memory every service cycle (a time interval specified by the system administrator - or calculated based on system resources).
The cache memory 30 includes a buffer pool 80. The buffer pool 80 is composed of a series of buffers as denoted by 90. The buffers 90 are tagged as either being used (filled with data blocks from the disk 10) or free (available to be used). The buffers that are tagged as being free, comprise the free buffer pool (buffers available for use).
In FIG. 1 when at least one of the clients 50, 60, or 70 first request data from the disk 10, the admissions controller 35 will check the cache memory 30 to determine if there are enough buffers 90 and bandwidth 20 to fulfill the request. If there are enough buffers 90 in the free buffer pool, and enough bandwidth 20, the admission controller 35, will allocate the buffers 90, so that the desired data blocks that a client will need could be stored in the buffers by the buffer manager 40 in every service cycle.
In the illustrative embodiment of FIG. 1 a continuous data file (denoted by 16 in FIG. 1) is composed of a series of contiguous blocks of data (denoted by A,B,C,D,E,F,G,H, and I in FIG. 1). For discussion purposes, lets assume that the continues data file 16 is video data, and the typical client displays a video and can perform Video Cassette Recorder (VCR) functions such as pause, resume, fast forward, jump and rewind. If the clients in the system are all reading data from the continuous data file 16, the location in the continuous data file 16, where a client is reading the data, can be denoted by 50a, 60a, and 70a (where 50a, 60a, and 70a, represent the positioning of clients 50, 60 and 70 relative to the continuous data file 16).
In the illustrative embodiment displayed in FIG. 2, client 50a may read block C next, client 60a may read block F next, and client 70a may read block J next. Therefore, with each service cycle, the clients move in a direction denoted by 17. When the clients move through the data in the direction denoted by 17 the clients are called forward progressing clients with respect to the block. When a client is expected to read a block of data after another client, the client that reads the data second is called the next forward progressing client with respect to the block of data. For example, 60a will read block F first, and then 50a will read block F. Therefore, with respect to block F, 50a is the next forward progressing client. Likewise, when clients are moving in the direction denoted by 18, the clients are considered backward progressing clients. For example, when client 60a reads data block E, then data block D, and then data block C, client 60a is considered a backward progressing client. Lastly, clients may fast forward, jump, pause, resume, and rewind within the continuous data file 16. For example, 50a may read block C and then jump to block G (this is comparable to a fast forward in a VCR), 60a may read block F and then backup and read block B (this is comparable to a rewind in a VCR), lastly, 50a may pause for a few service cycles and not read any data blocks (this is comparable to the pause command on a VCR).
The cache memory 30 serves a significant function in storage systems. For example, a client 50 may be displaying a video that is stored on the disk10. Without cache memory 30 the client would have to perform a full disk I/O to read each block of the continuous data filel6. The task of performing a full disk I/O becomes particularly problematic when the data is continuous data (e.g., the client needs the data to arrive at a specified rate to realize continues video or audio). Therefore the cache memory 30 serves a critical function. Instead of each client performing a disk I/O to retrieve each data block, the data can be prefetched and held in cache memory, which would be much quicker for the client to access (since cache memory is usually composed of very fast Random Access Memory (RAM)). In addition, if a second client 60, also needs to access the same data as accessed by the first client 50, the second client would be able to simultaneously read the data without having to go back to the disk 10.
However, there are times when a block of data needs to be prefetched by a client and that block of data is not in the buffer, either because it was not prefetched from the disk before a client needed it, or was prefetched and was removed from the buffer before the requesting client used it. When the data block is not in a data buffer when it needs to be prefetched by a client, this is typically called a cache miss. The performance of buffer replacement methods can be characterized by the number of cache misses that the system experiences. The number of cache misses is often defined by a cache miss ratio, which is the ratio of the total number of buffer cache misses to the total number of accesses to data blocks. The lower the number of cache misses the better the performance of the system. For example, a system with a 88% cache miss ratio is better than a system with 90% cache miss ratio because in an 88% cache miss ratio cache misses only occur 88% of the time.
In multimedia storage systems where there are several clients accessing the same data, the cache is designed so that each client can reserve a number of the buffers for its use, since displaying video would require that data be transferred to the client at a particular rate (r). As mentioned previously, a new client requesting data would not be admitted to the system unless the admissions controller 35 verifies that there is enough buffer space, and disk bandwidth available. By assuring that there is enough buffer space and disk bandwidth available, the admissions controller 35 assures that the buffer manager can facilitates the transfer of data to the client at the required rate (r) in subsequent service cycles. If d is the size of one buffer 90, and n.sub.B denoted by 80 is the total of all the buffers in the cache 30, then d*n.sub.B would be the total buffer space. Therefore a real time client (50,60,or 70), requiring access to data at the rate (r), would not be admitted to the system by the admissions controller 35, unless its buffer requirement together with the total sum of buffer requirements of existing admitted clients, was less than or equal to d*nB.
As previously discussed at the beginning of a service cycle the buffer manager 40, checks each client to determine which data block stored in the buffer 90 were used by the client, and which data blocks need to be prefetched from the disk 10, for the clients upcoming use. This task is accomplished by the following steps:
1. The buffers containing data blocks, which were consumed in the last service cycle, are added to the free buffer pool, if the buffers were not consumed by other clients in the last service cycle. PA1 2. The data blocks that need to be prefetched from disks in the current service cycle are determined. PA1 3. Whether a data block that needs to be prefetched from disk is already in the cache memory (in the free buffer pool) is determined. If so, the buffer is removed from the free buffer pool. PA1 4. For each block that needs to be prefetched and is not in the free buffer pool, a buffer, from the set of free buffers is allocated. PA1 5. Disk I/O is issued to retrieve the needed data blocks from the disks into the allocated buffers.
Step (4) given above is called the buffer replacement method. Currently there are several buffer replacement methods in use. For example, in the Least Recently Used (LRU) buffer replacement method, the buffer that contains the data blocks that were used least recently (used the longest ago), is chosen as the buffer that is allocated to receive new data blocks. In another buffer replacement method, Most Recently Used (MRU), the buffers that contain the data blocks that were used most recently (used last), are the buffers that are allocated to receive new data blocks. However, these buffer replacement methods produces cache miss ratios that are close to 100% when used with continuous media data storage systems. Therefore, it would be advantageous to have a buffer replacement method that has a cache miss ratio that is lower than MRU and LRU for continuous media data.
There is one final buffer replacement method known as the optimal method. The optimal method is a theoretical method that is used as a baseline in simulations. The optimal method allocates the buffer that contains data blocks that will not be referenced by the client for the longest period of time. The optimal method correctly anticipates the next time a data block will be accessed, and replaces buffers that will not be accessed for the longest period of time.
However, the optimal method is not realizable in a real world storage system because the optimal method requires that the buffer manager correctly anticipates the behavior of clients. This is not possible, because a client may read data continuously, pause on a particular block of data, resume after pausing on a data block, and jump around within a continuous data file. In addition a new client may arrive at any time. Therefore as stated above, the optimal method is only useful in simulations to benchmark buffer replacement methods. However it would be advantageous to have a buffer replacement method that approaches the performance (cache miss ratio) of the optimal method.